package Lee_code;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * @author blh
 * @date 2024年08月08日 8:46
 */
public class Lee_994_88 {
    public int orangesRotting(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        if (m == 1 && n == 1) {
            int temp = grid[0][0];
            if (temp==0){
                return 0;
            }
        }
        int okOrange = 0;
        // 感觉使用队列模拟比较好
        Deque<List<Integer>> deque = new ArrayDeque<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 将腐烂的句子入队
                if (grid[i][j] == 2) {
                    List<Integer> temp = new ArrayList<>();
                    temp.add(i);
                    temp.add(j);
                    deque.offer(temp);
                } else if (grid[i][j] == 1) {
                    okOrange++;
                }
            }
        }
        // 开始
        int minute = 0;
        boolean anyInfected = false;
        while (!deque.isEmpty()) {
            int size = deque.size();
            for (int i = 0; i < size; i++) {
                List<Integer> temp = deque.poll();
                int row = temp.get(0);
                int column = temp.get(1);
                if (row - 1 >= 0) {
                    if (grid[row - 1][column] == 1) {
                        grid[row - 1][column] = 2;
                        okOrange--;
                        anyInfected = true;
                        List<Integer> cur = new ArrayList<>();
                        cur.add(row - 1);
                        cur.add(column);
                        deque.add(cur);
                    }
                }
                if (row + 1 < m) {
                    if (grid[row + 1][column] == 1) {
                        grid[row + 1][column] = 2;
                        okOrange--;
                        anyInfected = true;
                        List<Integer> cur = new ArrayList<>();
                        cur.add(row + 1);
                        cur.add(column);
                        deque.add(cur);
                    }
                }
                if (column - 1 >= 0) {
                    if (grid[row][column - 1] == 1) {
                        grid[row][column - 1] = 2;
                        okOrange--;
                        anyInfected = true;
                        List<Integer> cur = new ArrayList<>();
                        cur.add(row);
                        cur.add(column - 1);
                        deque.add(cur);
                    }
                }
                if (column + 1 < n) {
                    if (grid[row][column + 1] == 1) {
                        grid[row][column + 1] = 2;
                        okOrange--;
                        anyInfected = true;
                        List<Integer> cur = new ArrayList<>();
                        cur.add(row);
                        cur.add(column + 1);
                        deque.add(cur);
                    }
                }
            }
            minute++;
            if (!anyInfected) {
                if (okOrange == 0) {
                    return minute;
                } else {
                    return -1;
                }

            }
            anyInfected = false;
        }
        return -1;
    }
}
